package com.hy.hash;

import java.util.*;

public class ThreeSum {

    /**
     * 第15题. 三数之和
     * 力扣题目链接
     *
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
     *
     * 注意： 答案中不可以包含重复的三元组。
     *
     * 示例：
     *
     * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     *
     * 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
     *
     * 思路
     * 注意[0， 0， 0， 0] 这组数据
     *
     * 哈希解法:
     *
     * 两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。
     * 把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。
     * 去重的过程不好处理，有很多小细节，如果在面试中很难想到位。
     * 时间复杂度可以做到O(n2)，但还是比较费时的，因为不好做剪枝操作。
     * 大家可以尝试使用哈希法写一写，就知道其困难的程度了。
     *
     */
    // hash 法
/*    public static List<List<Integer>> threeSum(int [] num){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(num);

        Map<Integer,Integer> map = new HashMap<>();
        for (int i : num) {
            for (int j : num) {
                int temp = i + j;
                if (map.containsKey(temp)){
                    map.put(temp,map.get(temp) + 1);
                }else {
                    map.put(temp,1);
                }
            }
        }
        for (int i : num) {
            if (map.containsKey(0 -i)){
                res.add()
            }
        }
        return res;
    }*/

    /**
     * 双指针法
     * @param num
     * @return
     */
    public static List<List<Integer>> threeSum2(int [] num){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(num);

        for (int i = 0; i < num.length; i++) {
            if (num[i] > 0 ){
                return res;
            }

            if (i > 0 && num[i] == num[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = num.length - 1;

            while (right > left ){
                int sum = num[i] + num[left] + num[right];
                if (sum > 0 ){
                    right --;
                }else if(sum < 0){
                    left ++;
                }else {
                    res.add(Arrays.asList(num[i],num[left],num[right]));
                    while (right >left && num[right] == num[right -1]) {
                        right--;
                    }
                    while (right > left && num[left] == num[left + 1]){
                        left --;
                    }
                    right --;
                    left --;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int [] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> res = threeSum2(nums);
        System.out.println("res: "+ res.toString());

       // System.out.println("res: "+ threeSum(nums));
    }
}
